package com.cat.dataStructure02;

import java.util.PriorityQueue;

/**
 * @author 曲大人的喵
 * @description https://leetcode.cn/problems/total-cost-to-hire-k-workers/
 * @create 2025/10/6 20:29
 * @since JDK17
 */

public class Solution03 {
    public long totalCost(int[] costs, int k, int candidates) {
        long ans = 0;
        int n = costs.length, pre = candidates, end = n - candidates - 1;
        PriorityQueue<int[]> heap = new PriorityQueue<>((a, b) -> {
            if (a[0] != b[0]) {
                return a[0] - b[0];
            }
            return a[1] - b[1];
        });
        for (int i = 0; i < candidates && i < n; i++) {
            heap.add(new int[]{costs[i], i});
        }
        for (int i = n - 1; i >= candidates && i >= n - candidates; i--) {
            heap.add(new int[]{costs[i], i});
        }
        for (int i = 0; i < k; i++) {
            var x = heap.poll();
            if (x[1] < pre && pre <= end) {
                heap.add(new int[]{costs[pre], pre});
                pre++;
            } else if (end >= pre) {
                heap.add(new int[]{costs[end], end});
                end--;
            }
            ans += x[0];
        }

        return ans;
    }
}
